It has become common for computer software developers to write programs making use of multiple threads of execution. Modern operating systems and programming languages support threads, and many large commercial applications are multithreaded. Threads are especially useful for implementing multiple asynchronous computations within an operating system process. Event-driven applications, for example, often employ multithreading.
The very features that make multithreading a useful programming technique also make debugging multithreaded programs a very difficult task, however. Multiple threads can interact in nondeterministic and timing-dependent ways. Typically such threads share data, requiring synchronization of their interaction to ensure program correctness, independent of how threads are scheduled or how their instruction streams are interleaved.
It is particularly difficult for programmers to detect errors in thread synchronization that are associated with race conditions. In a multithreaded program, a data race condition occurs when a shared memory location is accessed by two or more concurrent threads, with at least one of the accesses being a write, without proper synchronization to constrain the ordering of the accesses. The effects of the execution in such a case depend on the particular order in which the accesses take place. Race conditions often result in unexpected and undesirable program behavior, such as program crashes or incorrect results. Such nondeterminacy is also precisely why it is so difficult to detect race conditions using conventional debugging techniques.
Given the potentially detrimental effects of race conditions and the difficulty of debugging programs that contain them, automated tools for detecting the presence of race conditions should be of great value to developers of multithreaded programs. Effective and efficient tools have been lacking, however. With respect to dynamic race detection, in which an attempt is made to detect potential races in a particular execution of a program, two approaches have been widely used: the Lamport “happens-before” order and the lockset technique, which are described further in the detailed description below. The former typically has very unsatisfactory runtime overhead, especially for programs written in object-oriented languages like C# and Java, while the latter approach often produces an unacceptable number of false positives, particularly in programs using asynchronous delegates.